﻿#define _CRT_SECURE_NO_WARNINGS 1
//给你⼀个整数数组nums，返回数组answer，其中answer[i]等于nums中除nums[i]之外其余各
//元素的乘积。
//题⽬数据保证数组nums之中任意元素的全部前缀元素和后缀的乘积都在32位整数范围内。
//请不要使⽤除法，且在O(n)时间复杂度内完成此题
//eg:输⼊ : nums = [1, 2, 3, 4]   输出:[24, 12, 8, 6]
#include <iostream>
#include <vector>
using namespace std;

vector<int> productExceptSelf(vector<int>& nums)
{
	// lprod 表⽰：[0, i - 1] 区间内所有元素的乘积
	// rprod 表⽰：[i + 1, n - 1] 区间内所有元素的乘积
	int n = nums.size();
	vector<int> lprod(n + 1), rprod(n + 1);
	lprod[0] = 1, rprod[n - 1] = 1;// 预处理前缀积以及后缀积
	for (int i = 1; i < n; i++)
		lprod[i] = lprod[i - 1] * nums[i - 1];
	for (int i = n - 2; i >= 0; i--)
		rprod[i] = rprod[i + 1] * nums[i + 1];// 处理结果数组
	vector<int> ret(n);
	for (int i = 0; i < n; i++)
		ret[i] = lprod[i] * rprod[i];
	return ret;
}

int main()
{
	vector<int> nums({ 1,2,3,4 });
	vector<int> an=productExceptSelf(nums);
	for (auto i : an)
	{
		cout << i <<' ';
	}
	cout << endl;

	return 0;
}